Computer graphics systems are well known for displaying points, lines and character strings within a displayable screen region of a display device. It is often desirable to limit the lines, polygons etc. to a specific rectangular clipping region of the screen. Thus, given a line, and a clipping region, clipping algorithms are well known for drawing only pixels on a segment of the line which lies within the clipping region.
When the line segment is not identical to the line, a segment may be determined by several different methods, all of which have been found to be computationally intensive, resulting in slow graphics generation.
For the special case in which the clipping region is rectangular, the most commonly used algorithm is the Cohen-Sutherland clipping algorithm. A complete description of this prior art approach may be found in the text book "Fundamentals of Interactive Computer Graphics", revised edition, J. D. Foley and A Van Dam Addison Wesley, Reading, Massachusetts, July 1984.
The Cohen-Sutherland clipping algorithm categorizes lines as trivially rejected, trivially accepted, or as requiring further processing. When the line lies entirely within a clipping rectangle, or when the line segment is a null line, no further processing is required. By quickly identifying the lines which can be trivially accepted or rejected, the Cohen-Sutherland algorithm provides greatly improved graphics performance over the above-mentioned prior art approaches.
The Cohen-Sutherland algorithm generates a four bit outcode for each endpoint of the line segment. Each bit of the outcode is set to a logic "1" provided a given relation between the endpoint and the clipping region is true, as follows:
Bit 1: endpoint is above the clipping rectangle. PA1 Bit 2: endpoint is below the clipping rectangle. PA1 Bit 3: endpoint is to the left of the clipping rectangle. PA1 Bit 4: endpoint is to the right of the clipping rectangle. PA1 Bit 1: (y-ymin) PA1 Bit 2: (ymax-y) PA1 Bit 3: (xmin-x) and PA1 Bit 4: (x-xmax) PA1 (1) ((C.sub.0 BIT.sub.-- AND C.sub.1)!=0) is sufficient to indicate that the entire line segment lies outside the clipping rectangle (although not a necessary condition) PA1 (2) ((C.sub.0 BIT.sub.-- OR C.sub.1)=0) is a necessary condition for the entire line segment to lie inside the clipping angle.
Otherwise, the bit is false (i.e. set to a logic "0").
Table 1 illustrates the listing and orientation of the 4 bit outcodes generated by the Cohen-Sutherland algorithm relative to the four coordinates defining the clipping region (i.e. xmin, xmax, ymin, ymax).
TABLE 1 ______________________________________ 0101 0001 1001 (ymin) 0100 0000 1000 (ymax) 0110 0010 1010 (xmin) (xmax) ______________________________________
Prior art digital hardware has been developed for calculating the respective bits of the outcode by examining the sign-bit of the results of each of the following calculations:
C.sub.0 and C.sub.1 are defined according to the Cohen-Sutherland algorithm as the clip outcodes for the opposite endpoints of a line segment, and the following conditions can be tested:
If condition (1) is true, then the line segment is discarded because it must lie entirely outside the clipping rectangle.
If condition (2) is true, then the line segment lies entirely inside the clipping rectangle, and the line is drawn without further processing.
If neither condition holds, the line requires further processing to determine whether it lies partially inside or outside the clipping rectangle.
Many existing interactive computer graphics systems are capable of generating lines, polygons, etc. within a predetermined region known as the graphics device coordinate space which is often larger than the displayable screen region. According to the prior art Cohen-Sutherland clipping algorithm, all lines crossing the edge of the clipping rectangle into the graphic device coordinate space require further processing by a host processor. Studies have indicted that the additional processing time required to clip a line following the Cohen-Sutherland algorithm takes roughly 300 times longer than it takes to draw a line which does not require further processing.
In addition, because of the required additional processing for lines lying to the left of the clipping rectangle according to Cohen-Sutherland, this algorithm cannot be used to clip polygon boundary lines.